Many applications analyze and utilize multidimensional data, such as spatial data. Spatial data generally describes characteristics (e.g., location, size, shape, etc.) of geometric objects, such as points, lines, polygons, regions, surfaces, volumes, etc. Spatial data is used in many fields, such as computer-aided design, computer graphics, data management systems, robotics, image processing, geographic systems, pattern recognition, and computational geometry, just to name a few examples.
Spatial data can be stored in a spatial database. A spatial index is created in the database in order to facilitate efficient query execution. Different types of spatial indexes are known and examples of indexes include Grid, R-tree, and QuadTree.
In the process of building a spatial index for spatial objects, and sometimes in spatial query processing, the execution of spatial decomposition is needed. In spatial decomposition, the space is tessellated into a grid of tiles, and each spatial object is decomposed to the list of tiles it intersects. In image processing algorithms, the pixel is the basic unit of tessellated space, while in spatial decomposition the space is tessellated into a grid of tiles that can vary in their size.
Generally, the decomposition of points and line-strings is known and relatively straightforward. The decomposition of polygons, however, is more complicated and generally includes two processes: detecting the polygon border tiles, and then detecting the polygon interior tiles. This latter process can be complex.
Several algorithms exist for detecting the polygon interior tiles or filling or coloring the interior of the polygon. For example, the flood-fill algorithm starts with a point inside the polygon and recursively propagates color to neighboring pixels until either a border pixel or already colored pixel is reached. As another example, the scan conversion algorithm uses a horizontal scan line that advances through the polygon to detect intersecting points of the scan line with the polygon.
Prior polygon fill algorithms are not well suited for spatial decomposition of non-self-intersecting polygons. The flood-fill algorithm can fail to fill all interior pixels, for example, if a single pixel is crossed by more than one polygon edge. By contrast, the scan conversion algorithm can involve presorting the polygon edges and can be quite complex and time-consuming to implement.